The rising popularity of location-based services (LBS) is attributed to the high availability of inexpensive Global Position Systems (GPS), network bandwidth, and mobile devices with expanded storage and increased processing power. Mobile clients frequently use LBS applications to perform spatial queries based on their current locations. A popular type of spatial query is a range query.
A range query returns a collection of points of interest within a specified query range comprising a geographic circle. The query is sent to a server to process the query, and the server returns the result to the client via wireless networks. When the client's position changes, the result may be immediately invalidated and the client must continuously repost the query to the server to compute and retrieve updated results, incurring high network usage and processing costs.
Mobile Range Query (MRQ), also known as Moving Range Query, is defined as the retrieval of a range query result along with a safe region, also known as a safe zone or a validity region. As long as the user stays within the safe region, the current query result will remain unchanged; thereby the mobile client does not need to post another query.